public class MaxWater {
    // 接雨水问题
    // https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f?tpId=295&tqId=1002045&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public long maxWater (int[] arr) {
        // write code here
        // left数组记录每个元素左边的最高的柱子
        // right数组记录每个元素右边的最高的柱子
        int len = arr.length;
        int max = 0;
        int[] left = new int[len];
        int[] right = new int[len];
        for (int i = 0; i < len; i++) {
            left[i] = max;
            max = Math.max(max, arr[i]);
        }
        max = 0;
        for (int i = len-1; i >= 0; i--) {
            right[i] = max;
            max = Math.max(max, arr[i]);
        }
        int ret = 0;
        for (int i = 0; i < len; i++) {
            ret += Math.max((Math.min(left[i], right[i])-arr[i]), 0);
        }
        return ret;
    }
}
